1. Field of the Invention
The present invention relates to a scheduling method for high-level synthesis of a circuit which is represented by an operation description. More particularly, the present invention relates to a scheduling method for assigning a plurality of nodes included in a control flow graph respectively to a plurality of time steps so as to minimize the circuit area.
2. Description of the Related Art
In the prior art, xe2x80x9cHIGH-LEVEL SYNTHESIS, Introduction to Chip and System Design (Kluwer Academic Publishers) 1992xe2x80x9d describes a force-directed scheduling algorithm for performing a scheduling operation so as to minimize the circuit area. This algorithm calculates, for each time step, the sum of probabilities for a plurality of nodes included in a control flow graph to be assigned to that time step so as to estimate the circuit area (hereinafter, also referred to simply as the xe2x80x9careaxe2x80x9d) based on the maximum value of the calculated sums.
Japanese Laid-Open Publication No. 9-81605 describes an algorithm which involves an improvement to the above force-directed scheduling algorithm. This algorithm gradually narrows down the scheduling candidates by calculating the estimated.value of the circuit area, for each node (B) having scheduling candidate (A) in the time step for which the sum of probabilities is maximum, with the scheduling candidate (A) having been excluded from a list of one or more scheduling candidates of the node (B), so as to obtain a combination of a node (C) and a scheduling candidate (D) for which the circuit area is maximum, and then excluding the scheduling candidate (D) from a list of one or more scheduling candidates of the node (C). The algorithm described in Japanese Laid-Open Publication No. 9-81605 aims to solve a problem associated with the force-directed scheduling algorithm (i.e., the optimal time step may be excluded from the list of scheduling candidates when a plurality of nodes are assigned to time steps at once, thereby resulting in a local solution). Thus, the algorithm described in Japanese Laid-Open Publication No. 9-81605 gradually narrows down the scheduling candidates, thereby achieving better scheduling results than those obtained with the force-directed scheduling algorithm.
However, the algorithm described in Japanese Laid-Open Publication No. 9-81605 calculates; for each time step, the sum of probabilities for a plurality of nodes to be assigned to that time step, and calculates the estimated value of the circuit area, for each node (B) having scheduling candidate (A) in the time step for which the sum of probabilities is maximum, with the scheduling candidate (A) having been excluded from a list of one or more scheduling candidates of the node (B). Thus, the accuracy of the estimated value may not be sufficient, whereby the optimal time step may be excluded from the list of scheduling candidates, thereby resulting in a local solution.
Moreover, the algorithm described in Japanese Laid-Open Publication No. 9-81605 does not take into consideration the area of registers. Therefore, it is likely that even when the area of operators is reduced, the area of registers increases, thereby increasing the area of the entire circuit.
According to one aspect of this invention, there is provided a scheduling method for high-level synthesis of a circuit which is represented by an operation description. The method includes the steps of: (a) calculating a probability for each of a plurality of nodes included in a control flow graph to be assigned to a time step; (b) calculating a sum of the probabilities for each time step; (c) calculating, for each node having a scheduling candidate in a time step for which the sum of probabilities is maximum, an estimated value of an area of the circuit with the node having been temporarily assigned to the scheduling candidate; (d) retrieving a combination of a node and a scheduling candidate for which the estimated value is maximum: and (e) narrowing down a list of scheduling candidates of the node in the combination by excluding the scheduling candidate in the combination from the list of scheduling candidates of the node in the combination.
In one embodiment of the invention, the method further includes the step of determining whether or not there is more than one combination of a node and a scheduling candidate retrieved in the step (d) for which the estimated value is maximum. If it is determined that there is more than one such combination, the step (e) includes the steps of: (e-1) calculating a value of a predetermined evaluation function for each of the combinations; (e-2) retrieving a combination of a node and a scheduling candidate for which the value of the predetermined evaluation function is maximum; and (e-3) excluding the scheduling candidate in the combination from the list of scheduling candidates of the node in the combination.
In one embodiment of the invention, the evaluation function is represented by ((the number of inputs of the node)xe2x88x92(the number of outputs of the node)xc3x97(a time step number of the scheduling candidate).
According to another aspect of this invention, there is provided a computer-readable recording medium having a program recorded thereon for instructing a computer to execute a scheduling method for high-level synthesis of a circuit which is represented by an operation description. The scheduling method includes the steps of: (a) calculating a probability for each of a plurality of nodes included in a control flow graph to be assigned to a time step; (b) calculating a sum of the probabilities for each time step; (c) calculating, for each node having a scheduling candidate in a time step for which the sum of probabilities is maximum, an estimated value of an area of the circuit with the node having been temporarily assigned to the scheduling candidate; (d) retrieving a combination of a node and a scheduling candidate for which the estimated value is maximum; and (e) narrowing down a list of scheduling candidates of the node in the combination by excluding the scheduling candidate in the combination from the list of scheduling candidates of the node in the combination.
Thus, the invention described herein makes possible the advantage of: (1) providing a scheduling method for high-level synthesis capable of quickly and accurately calculating the estimated value of the circuit area; and (2) providing a scheduling method for fast high-level synthesis which takes into consideration the area of registers.